package 剑指offer;

/**
 输入: [3,2,1,5,6,4] 和 k = 2
 输出: 5
 示例 2:
 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 输出: 4
 */

public class _215数组中的第K个最大元素 {

    public int findKthLargest(int[] nums, int k) {
        int n =nums.length-1;

        quickSort(nums,0,n);

        return nums[n+1-k];
    }

    public void quickSort(int[] nums,int low,int high){
        if(low<high){
            int mid =getMiddle(nums,low,high);
            quickSort(nums,low,mid-1);
            quickSort(nums,mid+1,high);
        }

    }
    private static int getMiddle(int[] a, int low, int high){

        int temp=a[low];
        while(low<high){

            while(low<high && a[high]>temp){
                high--;
            }
            a[low]=a[high];
            while(low<high && a[low]<=temp){
                low++;
            }
            a[high]=a[low];

        }
        a[low]=temp;
        return low;

    }
}
